/**
 * \file	ArbreAVL.h
 * \brief	Définition de la classe ArbreAVL
 * \author	Thibaut ALGRIN
 * \author	Emmanuel CARRE
 * \version	0.1
 * \date	Decembre 2011
 */

#ifndef ARBRE_AVL_H_
#define ARBRE_AVL_H_

#include <stdexcept>
#include <iostream>
#include <vector>
#include <queue>

/**
 * \namespace tp3
 *
 * Espace de noms pour le TP3.
 */
namespace tp3
{

/**
 * \class	ArbreAVL
 *
 * \brief	classe générique représentant un arbre.
 *
 *  La classe gère un arbre générique.
 *  L'implémentation se fait par chaînage.
 */
template<typename TypeCle, typename TypeValeur>
class ArbreAVL
{
public:
	/**
	 * \brief	Constructeur
	 *
	 * \post	Une instance de la classe ArbreAVL est initialisée.
	 *
	 */
	ArbreAVL();

	/**
	 * \brief	Constructeur de copie
	 *
	 * \pre		Il faut qu'il y ait suffisamment de mémoire
	 *
	 * \post	Une copie profonde de l'arbre source est instanciée
	 *
	 * \exception bad_alloc s'il n'y a pas assez de mémoire
	 */
	ArbreAVL(const ArbreAVL<TypeCle, TypeValeur>& source)	throw(std::bad_alloc);

	/**
	 *  \brief	Destructeur
	 *
	 *  \post	L'instance de l'arbre est détruite
	 */
	~ArbreAVL();

	/*
	 * \brief	Insertion dans l'ordre de tri avec balancement
	 * \post	L'élément est inséré dans l'abre qui est ré-équilibré si nécessaire
	 *
	 * \exception	bad_alloc	Mémoire insuffisante
	 */
	void inserer(const TypeCle& cle, const TypeValeur& valeur);

	/*
	 * \brief	Trouver une valeur à une clé donnée.
	 * \post	La valeur correspondante à la clé est retournée
	 * \post	L'arbre est inchangé
	 *
	 * \exception	logic_error	La clé n'existant
	 */
	TypeValeur valeur(const TypeCle& cle) const;

	/*
	 * \brief	Enlever un élément dans l'arbre tout en conservant le balancement.
	 * \post	L'élément correspondant à la clé a été supprimé
	 *
	 * \exception	logic_error	La clé n'existe pas
	 * \exception	logic_error	L'arbre est vide
	 */
	void enlever(const TypeCle& cle)		throw(std::logic_error);

	/**
	 * \brief Vérifier si l'arbre est vide
	 *
	 * \post L'arbre est inchangé
	 *
	 */
	bool estVide() const;

	/**
	 * \brief Retourner le nombre d'éléments dans l'arbre
	 *
	 * \post L'arbre est inchangé
	 *
	 */
	long taille() const;

	/**
	 *  \brief Retourner la hauteur de l'arbre
	 *
	 * La détermination de la hauteur se fait par parcours de l'arbre
	 *
	 * \pre L'arbre n'est pas vide
	 *
	 * \post L'arbre est inchangé
	 *
	 * \exception logic_error si l'arbre est vide
	 *
	 */
	int hauteur() const	throw(std::logic_error);

	/**
	 *  \brief Retourner le parent d'un élément dans l'arbre
	 *
	 * \pre L'arbre n'est pas vide
	 * \pre L'élément fait partie de l'arbre
	 *
	 * \post L'arbre est inchangé
	 *
	 * \exception logic_error si l'arbre est vide
	 * \exception logic_error si l'élément n'est pas dans l'arbre
	 *
	 */
	std::pair<TypeCle, TypeValeur> parent(const TypeCle&)	throw(std::logic_error);

	/**
	 *  \brief Retourner le successeur d'un élément dans l'arbre
	 *
	 * \pre L'arbre n'est pas vide
	 * \pre L'élément fait partie de l'arbre
	 * \pre L'élément n'est pas le maximum dans l'arbre
	 *
	 * \post L'arbre est inchangé
	 *
	 * \exception logic_error si l'arbre est vide
	 * \exception logic_error si l'élément n'est pas dans l'arbre
	 * \exception logic_error si l'élément est le maximum dans l'arbre
	 *
	 */
	std::pair<TypeCle, TypeValeur> successeur(const TypeCle&)	throw(std::logic_error);

	/**
	 *  \brief Lister un arbre en en-ordre
	 *
	 * Le listage se fait dans un vector
	 *
	 * \pre Il y a assez de mémoire
	 *
	 * \post L'arbre est inchangé
	 *
	 * \exception bad_alloc s'il n'y a pas assez de mémoire
	 *
	 */
	std::vector<std::pair<TypeCle, TypeValeur> > lister() const	throw(std::bad_alloc);

	/**
	 *  \brief Lister un arbre en pré-ordre
	 *
	 * Le listage se fait dans un vector
	 *
	 * \pre Il y a assez de mémoire
	 *
	 * \post L'arbre est inchangé
	 *
	 * \exception bad_alloc s'il n'y a pas assez de mémoire
	 *
	 */
	std::vector<std::pair<TypeCle, TypeValeur> > listerPreOrdre() const	throw(std::bad_alloc);

	/**
	 *  \brief Vérifier si un élément est dans l'arbre
	 *
	 * \post L'arbre est inchangé
	 *
	 */
	bool appartient(const TypeCle &) const;

	//surcharge d'opérateurs

	/**
	 * \brief Surcharger l'opérateur =
	 *
	 * \pre Il y a assez de mémoire pour l'opération
	 *
	 * \post Une copie profonde de l'arbre a est créée
	 * \post Une référence sur l'élément courant est retournée.
	 *
	 * \exception bad_alloc si la mémoire est insuffisante
	 *
	 */
	ArbreAVL<TypeCle, TypeValeur>& operator =(const ArbreAVL<TypeCle, TypeValeur> & a)	throw(std::bad_alloc);

	/**
	 * \brief Surcharger l'opérateur ==
	 *
	 * \post Les 2 opérandes (arbres) sont inchangés
	 *
	 */
	bool operator ==(const ArbreAVL<TypeCle, TypeValeur> &a) const;

	/**
	 * \brief	Affiche le contenu de l'arbre
	 * \pre		L'opérateur << doit exister pour TypeCle et TypeValeur
	 *
	 */
	void       show();
private:
	/**
	 * \class Noeud
	 *
	 * \brief classe interne représentant un noeud typique de l'arbre
	 *
	 *  La classe représente un noeud typique
	 *  pour implémenter un arbre par chaînage.
	 */
	class Noeud
	{
	public:
		TypeCle cle;		/*!< La donnée dans l'arbre*/
		TypeValeur valeur;	/*!< La donnée dans l'arbre*/
		Noeud *gauche;		/*!< Pointeur vers le fils gauche*/
		Noeud *droite;		/*!< Pointeur vers le fils droit*/
		int hauteur;		/*!< La hauteur d'un noeud, utile pour le critère de balancement*/
		/**
		 * \brief Constructeur de la classe Noeud
		 *
		 * \post un noeud typique est intialisé
		 *
		 */
		Noeud(const TypeCle& c, const TypeValeur& v) :
			cle(c), valeur(v), gauche(0), droite(0), hauteur(0)
		{
		}
		bool      operator==(Noeud *b);
	};

	// Les données membres
	Noeud * racine;			/*!< La racine de l'arbre*/
	long cpt;				/*!< Nombre de noeuds dans l'arbre*/


	/**
	 *  \brief Insérer élément dans un sous-arbre
	 *
	 * Fonction auxiliaire (récursive). Insertion avec balancement
	 *
	 * \post Le sous-arbre contient un élément de plus
	 */
	void	_auxInsererAVL(Noeud *&arbre, const TypeCle cle, const TypeValeur &val)	throw(std::bad_alloc);

	int	_hauteur(Noeud *arb) const;

	Noeud* _auxAppartient(Noeud* arbre, const TypeCle &cle, const TypeValeur &val) const;
	Noeud* _auxAppartient(Noeud* arbre, const TypeCle &) const;
	void _zigZigGauche(Noeud *&);
	void _zigZigDroit(Noeud *&);
	void _zigZagGauche(Noeud *&);
	void _zigZagDroit(Noeud *&);
	int  _maximum(int, int) const;
	void _auxCopier(Noeud *source, Noeud *&destination) throw(std::bad_alloc);
	void	_auxEnleverAVL(Noeud * & t, const TypeCle & cle);
	/**
	 * \fn void ArbreAVL<TypeCle, TypeValeur>::_auxRetireMin( Noeud* & t) const throw(logic_error)
	 *
	 * \param[in] t Le sous-arbre dans lequel on fait l'enl�vement
	 */
	void _auxRetireMin( Noeud* & t) const throw(std::logic_error);
	/**
	 * \fn void Arbre<E>:: _auxEnOrdre(Noeud* arb, vector<E>& v) const
	 *
	 * \param[in] arb Le sous-arbre � parcourir
	 * \param[out] v Le vector qui contient le listage du sous-arbre
	 */
	void        _auxEnOrdre(Noeud* arb, std::vector<std::pair<TypeCle, TypeValeur> >& v) const;
	void        _auxPreOrdre(Noeud* arb, std::vector<std::pair<TypeCle, TypeValeur> >& v) const;
	Noeud*      _parent(Noeud* arb, Noeud *sArb) const throw(std::logic_error);
	void         _show(Noeud*);
	std::pair<TypeCle, TypeValeur> _successeur(Noeud* arb, const TypeCle & info) throw (std::logic_error);
	TypeCle	_max(Noeud *arb) const;
	TypeCle	_min(Noeud *arb) const;
};

}

#include "ArbreAVL.inl"

#endif

